#include <iostream>
#include <vector>
#include <queue>
using namespace std;

class AnimalShelf {
private:
    vector<queue<int>> shelves;
public:
    AnimalShelf() {
        shelves.emplace_back(queue<int>());
    }
    
    void enqueue(vector<int> animal) {
        shelves[animal[1]].push(animal[0]);
    }
    
    vector<int> dequeueAny() {
        if(shelves[0].empty() && shelves[1].empty())
            return {-1,-1};
        int cat = shelves[0].empty() ? 20001 : shelves[0].front();
        int dog = shelves[1].empty() ? 20001 : shelves[1].front();
        if(cat <= dog) return dequeueCat();
        else return dequeueDog();
    }
    
    vector<int> dequeueDog() {
        if(shelves[1].empty()) return {-1,-1};
        vector<int> res = {shelves[1].front(),1};
        shelves[1].pop();
        return res;
    }
    
    vector<int> dequeueCat() {
        if(shelves[0].empty()) return {-1,-1};
        vector<int> res = {shelves[0].front(),0};
        shelves[0].pop();
        return res;
    }
};


int main()
{
    return 0;
}